package com.wu.leetcode.leetcode148;

import java.util.ArrayList;

/**
 * Leetcode148-排序链表
 *
 * @author lynn
 * @date 2020/8/21 - 16:34
 */


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

// 4->2->1->3
class Solution {
    public static ListNode sortList(ListNode head) {
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        int[] arr = new int[len];
        ListNode res = head;
        int index = 0;
        while (res != null) {
            arr[index] = res.val;
            index++;
            res = res.next;
        }
        mergeSort(arr, 0, arr.length - 1);
        ListNode listNode = new ListNode(32343);
        ListNode tem = listNode;
        for (int i = 0; i < arr.length; i++) {
            tem.next = new ListNode(arr[i]);
            tem = tem.next;
        }
        return listNode.next;
    }

    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            //向左分解
            mergeSort(arr, left, mid);
            //向右分解
            mergeSort(arr, mid + 1, right);

            //合并
            merge(arr, left, right, mid);
        }
    }

    /**
     * 合并
     *
     * @param arr   待排序的数组
     * @param left  左边已排序的子数组
     * @param right 右边已排序的子数组
     * @param mid   划分两个数组的索引
     */
    public static void merge(int[] arr, int left, int right, int mid) {
        //左边数组的起始位置
        int l = left;
        //右边数组的起始位置
        int r = mid + 1;
        //初始化临时数组的长度
        int[] temp = new int[right - left + 1];
        //临时数组的起始位置
        int t = 0;

        //1.将左右两边的数据按照规则填入temp数组
        while (l <= mid && r <= right) {
            //判断并比较，数据依次填入
            temp[t++] = arr[l] <= arr[r] ? arr[l++] : arr[r++];
        }
        //检测哪边未完全填入 将其依次填入
        while (l <= mid) {
            temp[t++] = arr[l++];
        }
        while (r <= right) {
            temp[t++] = arr[r++];
        }
        //将temp数组复制到arr
        //注意 不是每次拷贝都是所有的数据
        // 把最终的排序的结果复制给原数组
        for (int i = 0; i < temp.length; i++) {
            arr[left + i] = temp[i];
        }
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(4);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        ListNode listNode = sortList(node1);
    }
}